/**
  * Author: Mei
  * Date: 2020-12-13 15:11
  * Description:
  * 容器一般分为序列式、关联式、不定序的容器(Unordered Containers)底层是hashtable(11新加）
  *
  */
#include "../../head.h"

using namespace std;

#define Size 500000

long get_a_target_long() {
    long target = 0;
    cout << "target (0." << endl;
}

int compareLongs(const void *a, const void *b) {
    return (*(long *) a - *(long *) b);
}

int compareStrings(const void *a, const void *b) {
    if (*(string *) a > *(string *) b) {
        return 1;
    } else if (*(string *) a < *(string *) b) {
        return -1;
    } else {
        return 0;
    }
}

int main() {
    /**
     * Array
     * Vector
     * Deque(双向队列）
     * List（双向链表）
     * Forward_List(单向链表）
     *
     */

    /**
     * 都采用红黑树
     * Set/Multiset（可重复/不可重复）
     * Map/Multimap
     *
     */
    array<long, Size> arr;
    clock_t timeStart = clock();
    for (long i = 0; i < Size; ++i) {
        arr[i] = rand();
    }
    cout << "mill-seconds: " << (clock() - timeStart) << endl;
    cout << "array.size() = " << arr.size() << endl;
    cout << "array.front() = " << arr.front() << endl;
    cout << "array.back() = " << arr.back() << endl;
    cout << "array.data() = " << arr.data() << endl;
    //排序
    long target = 100;
    timeStart = clock();
    //快排
    qsort(arr.data(), Size, sizeof(long), compareLongs);
    //查找之前需要有序
    long *pItem = (long *) bsearch(&target, (arr.data()), Size, sizeof(long), compareLongs);
    cout << "qsort()+bsearch()--mill-seconds: " << (clock() - timeStart) << endl;
    if (pItem != NULL) {
        cout << "found." << *pItem << endl;
    } else {
        cout << "not found!" << endl;
    }

    /**
     * 执行结果
     *  mill-seconds: 113
        array.size() = 500000
        array.front() = 41
        array.back() = 29794
        array.data() = 0x437980
        qsort()+bsearch()--mill-seconds: 200
        found.100
     *
     */
    return 0;
}